/* 设计算法判断无向图是否是一棵树 */

#include <iostream>
#include "algraph.h"
using namespace std;

// 深度优先搜索 -- 找到点的个数和边的个数
void fun(ALGraph *G, int v, int &vn, int &en, int visit[])
{
  // 访问开始结点
  visit[v] = 1;
  
  // 记录点的个数
  ++vn;
  
  // 找到开始结点的邻接结点
  ArcNode *p = G->adjlist[v].firstarc;
  
  // 如果邻接结点不为空
  while (p != NULL)
  {
    // 记录边的个数
    ++en;
    
    // 邻接结点未被访问过
    if (visit[p->adjvex] == 0)
      fun(G, p->adjvex, vn, en, visit); // 以邻接结点为开始结点，深度优先搜索
    
    // 到下一个邻接结点
    p = p->nextarc;
  }
}

// 判断图是否为树
bool GisTree(ALGraph *G)
{
  int vn = 0, en = 0;
  
  // 标记结点是否被访问
  int visit[maxsize];
  
  // 初始时，结点均未被访问
  for (int i = 0; i < G->numver; ++i)
    visit[i] = 0;
  
  // 找图中 结点的个数和边的个数
  fun(G, 1, vn, en, visit);
  
  // 结点的个数和边的个数满足要求
  if (vn == G->numver && (G->numver - 1) == en / 2)
    return true;
  else
    return false;
}

int main()
{
  // 创建图 -- 邻接表
  ALGraph *G = create_algraph(4, 3);
  
  // 判断图是否为树
  if (GisTree(G))
    cout << "是树！";
  else
    cout << "不是树！";
  return 0;
}